package mpicbg.models;


public class quickSort

{
	       
	public static void sort(Float array[], Float s[][], int start, int end)
	{
		
	        int i = start;                          // index of left-to-right scan
	        int k = end;                            // index of right-to-left scan

	        if (end - start >= 1)                   // check that there are at least two elements to sort
	        {
	                float pivot = array[start];       // set the pivot as the first element in the partition

	                while (k > i)                   // while the scan indices from left and right have not met,
	                {
	                        while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
	                                i++;                                    // element greater than the pivot
	                        while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
	                            k--;                                        // element not greater than the pivot
	                        if (k > i)                                       // if the left seekindex is still smaller than
	                                swap(array,  s, i, k);                      // the right index, swap the corresponding elements
	                }
	                swap(array,  s, start, k);          // after the indices have crossed, swap the last element in
	                                                // the left partition with the pivot 
	                sort(array,  s, start, k - 1); // quicksort the left partition
	                sort(array,  s, k + 1, end);   // quicksort the right partition
	        }
	        else    // if there is only one element in the partition, do not do any sorting
	        {
	                return;                     // the array is sorted, so exit
	        }
	}



	public static void swap(Float array[], Float s[][], int index1, int index2) 
	// pre: array is full and index1, index2 < array.length
	// post: the values at indices 1 and 2 have been swapped
	{
		Float temp = array[index1];           // store the first value in a temp
		Float[] a1 = s[index1];
		array[index1] = array[index2];      // copy the value of the second into the first
		s[index1] = s[index2];
		array[index2] = temp;               // copy the value of the temp into the second
		s[index2] = a1;
	}



public static void sort(float array[], float d[], String s[], int start, int end)
{
	
        int i = start;                          // index of left-to-right scan
        int k = end;                            // index of right-to-left scan

        if (end - start >= 1)                   // check that there are at least two elements to sort
        {
                float pivot = array[start];       // set the pivot as the first element in the partition

                while (k > i)                   // while the scan indices from left and right have not met,
                {
                        while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
                                i++;                                    // element greater than the pivot
                        while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
                            k--;                                        // element not greater than the pivot
                        if (k > i)                                       // if the left seekindex is still smaller than
                                swap(array, d, s, i, k);                      // the right index, swap the corresponding elements
                }
                swap(array, d, s, start, k);          // after the indices have crossed, swap the last element in
                                                // the left partition with the pivot 
                sort(array, d, s, start, k - 1); // quicksort the left partition
                sort(array, d, s, k + 1, end);   // quicksort the right partition
        }
        else    // if there is only one element in the partition, do not do any sorting
        {
                return;                     // the array is sorted, so exit
        }
}



public static void swap(float array[], float d[], String s[], int index1, int index2) 
// pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped
{
	float temp = array[index1];           // store the first value in a temp
	float tempd = d[index1];
	String a1 = s[index1];
	array[index1] = array[index2];      // copy the value of the second into the first
	d[index1] = d[index2];
	s[index1] = s[index2];
	array[index2] = temp;               // copy the value of the temp into the second
	d[index2] = tempd;
	s[index2] = a1;
}

public static void sort(float array[], float d[], float s[][], int start, int end)
{
	
        int i = start;                          // index of left-to-right scan
        int k = end;                            // index of right-to-left scan

        if (end - start >= 1)                   // check that there are at least two elements to sort
        {
                float pivot = array[start];       // set the pivot as the first element in the partition

                while (k > i)                   // while the scan indices from left and right have not met,
                {
                        while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
                                i++;                                    // element greater than the pivot
                        while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
                            k--;                                        // element not greater than the pivot
                        if (k > i)                                       // if the left seekindex is still smaller than
                                swap(array, d, s, i, k);                      // the right index, swap the corresponding elements
                }
                swap(array, d, s, start, k);          // after the indices have crossed, swap the last element in
                                                // the left partition with the pivot 
                sort(array, d, s, start, k - 1); // quicksort the left partition
                sort(array, d, s, k + 1, end);   // quicksort the right partition
        }
        else    // if there is only one element in the partition, do not do any sorting
        {
                return;                     // the array is sorted, so exit
        }
}



public static void swap(float array[], float d[], float s[][], int index1, int index2) 
// pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped
{
	float temp = array[index1];           // store the first value in a temp
	float tempd = d[index1];
	float[] a1 = s[index1];
	array[index1] = array[index2];      // copy the value of the second into the first
	s[index1] = s[index2];
	d[index1] = d[index2];
	array[index2] = temp;               // copy the value of the temp into the second
	d[index2] = tempd;
	s[index2] = a1;
}

public static void sort(float array[], float s[][], int start, int end)
{
	
        int i = start;                          // index of left-to-right scan
        int k = end;                            // index of right-to-left scan

        if (end - start >= 1)                   // check that there are at least two elements to sort
        {
                float pivot = array[start];       // set the pivot as the first element in the partition

                while (k > i)                   // while the scan indices from left and right have not met,
                {
                        while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
                                i++;                                    // element greater than the pivot
                        while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
                            k--;                                        // element not greater than the pivot
                        if (k > i)                                       // if the left seekindex is still smaller than
                                swap(array,  s, i, k);                      // the right index, swap the corresponding elements
                }
                swap(array,  s, start, k);          // after the indices have crossed, swap the last element in
                                                // the left partition with the pivot 
                sort(array,  s, start, k - 1); // quicksort the left partition
                sort(array,  s, k + 1, end);   // quicksort the right partition
        }
        else    // if there is only one element in the partition, do not do any sorting
        {
                return;                     // the array is sorted, so exit
        }
}



public static void swap(float array[], float s[][], int index1, int index2) 
// pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped
{
	float temp = array[index1];           // store the first value in a temp
	float[] a1 = s[index1];
	array[index1] = array[index2];      // copy the value of the second into the first
	s[index1] = s[index2];
	array[index2] = temp;               // copy the value of the temp into the second
	s[index2] = a1;
}


public static void sort(String array[], float s[], int start, int end)
{
	
        int i = start;                          // index of left-to-right scan
        int k = end;                            // index of right-to-left scan

        if (end - start >= 1)                   // check that there are at least two elements to sort
        {
                String pivot = array[start];       // set the pivot as the first element in the partition

                while (k > i)                   // while the scan indices from left and right have not met,
                {
                        while (array[i].compareTo( pivot ) <=0 && i <= end && k > i)  // from the left, look for the first
                                i++;                                    // element greater than the pivot
                        while (array[i].compareTo( pivot ) >0 && k >= start && k >= i) // from the right, look for the first
                            k--;                                        // element not greater than the pivot
                        if (k > i)                                       // if the left seekindex is still smaller than
                                swap(array,s, i, k);                      // the right index, swap the corresponding elements
                }
                swap(array,s, start, k);          // after the indices have crossed, swap the last element in
                                                // the left partition with the pivot 
                sort(array,s, start, k - 1); // quicksort the left partition
                sort(array,s, k + 1, end);   // quicksort the right partition
        }
        else    // if there is only one element in the partition, do not do any sorting
        {
                return;                     // the array is sorted, so exit
        }
}



public static void swap(String array[],float s[], int index1, int index2) 
// pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped
{
	String temp = array[index1];           // store the first value in a temp
	float a1 = s[index1];
	array[index1] = array[index2];      // copy the value of the second into the first
	s[index1] = s[index2];
	array[index2] = temp;               // copy the value of the temp into the second
	s[index2] = a1;
}

}